/**
 * @file sudoku.cpp
 * Main file for implementation of resolving sudoku problem
 *
 * @author  Wilq
 * @version 0.1 
 */

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


/**
* Klasa rozwiązująca problem sudoku
* 
 */

class Sudoku{
    private:
        /* Rozmiar tablicy n x n */
        const int m_size;
        /* Ilość wszystkich pól */ 
        const int m_size2;
        /* Ilość pustych pól */ 
        int num_empty;
        /* Ilość juz zapełnionych pól */ 
        int num_puts;
        /* Tablica przechowywująca dane wejściowe */ 
        char **ma_cells;
        /* Tablica przechowywująca maski dozwolonych wartości (liczby nie ujemne) lub liczby wstawione (libczby ujemne) */ 
        int **ma_nt; 
        /* Tablica przechowywująca ilość wykreślonych liczb z danej komórki */ 
        int **ma_num;
    
        //Prywatny !! Kontruktor kopiujący - macierzy ma_cells - nie kopiuje 
        Sudoku(const Sudoku& sudoku,int a):m_size(sudoku.m_size),m_size2(sudoku.m_size2)
        {
            ma_cells = NULL;// sudoku.ma_cells;
            ma_nt = new int*[m_size];
            ma_num= new int*[m_size];

            for(int i = 0 ; i < m_size ; i++)
            {
                ma_nt[i] = new int[m_size];
                ma_num[i] = new int[m_size];
                for(int j = 0; j< m_size;j++)
                {
                    ma_nt[i][j] = sudoku.ma_nt[i][j];
                    ma_num[i][j] = sudoku.ma_num[i][j];
                }
            }
            num_puts = sudoku.num_puts;
            num_empty = sudoku.num_empty;
        }


        void create_solution(Sudoku* p_sudoku)
        {
            int ** temp = ma_nt;

            ma_nt = p_sudoku->ma_nt;
            p_sudoku->ma_nt = temp;

            temp = ma_num;
            ma_num = p_sudoku->ma_num;
            p_sudoku->ma_num = temp;

            delete p_sudoku;

            minus_tab();
        }

        void minus_tab()
        {
            for( int i = 0; i < m_size ; i++)
                for( int j = 0; j < m_size ; j++)
                    ma_nt[i][j] = - ma_nt[i][j];
        }

        int check_condition()
        {
            int flag = -1;
            for( int i = 0; i < m_size ; i++)
                for( int j = 0; j < m_size ; j++)
                {
                    if( ma_nt[i][j] < 0)
                    {
                        if( check_row( ma_nt[i][j],i,j) ||  
                            check_column( ma_nt[i][j],i,j) || 
                            check_square( ma_nt[i][j],i,j) ) 
                        {
                            #if DEBUG
                                printf("Condition Fail: i = %d,j = %d i j = %d\n",i,j,-ma_nt[i][j]);
                            #endif
                            return 1; 
                        }
                    }
                    else
                    {    
                        flag = 0;
                    }

                }
            return flag;
        }

        int check_row(int n, int i, int j){
            for(int move = 0; move < m_size ; move ++)
            {
                if( j == move ) continue;
                if( ma_nt[i][move] == n )
                {
                    return 1;
                }
            }
            return 0;
        }  

        int check_column(int n, int i, int j){ 
            for(int move = 0; move < m_size ; move ++)
            {
                if( i == move ) continue;
                if( ma_nt[move][j] == n )
                {
                    return 1;
                }
            }
            return 0;
        }

        int check_square(int n, int i, int j){
            int sq = sqrt(m_size);// szerokosc kazdego kwadratu
            int square_i = i/sq; // pozycja i dla podanego kwadratu 
            int square_j = j/sq; // pozycja j dla podanego kwadratu 
            for(int move_i = square_i*sq; move_i < (square_i+1)*sq ; move_i++)
                for(int move_j = square_j*sq; move_j < (square_j+1)*sq; move_j++)
                {
                    if( move_i == i && move_j == j)
                        continue;
                    if( ma_nt[move_i][move_j] == n )
                    {
                        return 1;
                    }
                }
            return 0;
        } 

        Sudoku* try_resolve(int arg)
        {
            int maks_old = arg;

            #if DEBUG
                static int debug_print = 0;
                debug_print++;
            #endif

            for( int i = 0; i < m_size ; i=(i+1)%m_size )
                for( int j = 0; j < m_size ; j++ )
                {
                    if( ma_num[i][j] >= m_size - maks_old)
                    {
                        int n = 1;
                        int failed = 0;
                        while( n <= check_mask(ma_nt[i][j]) )
                        {
                            Sudoku * rec = new Sudoku(*this,2);
                            #if DEBUG
                                for(int temp = 0; temp < debug_print ; temp++)
                                    printf(" ");
                                printf("Recursion value = %d, i = %d, j = %d num = %d\n",check((*rec).ma_nt[i][j], n),i,j,check_mask(ma_nt[i][j])); 
                            #endif
                            (*rec).update( check((*rec).ma_nt[i][j], n) , i ,j);
                            (*rec).update_on_elimination();
                            int con = (*rec).check_condition();
                            if( con == 1 )
                            {
                                failed++;
                                if(failed == check_mask(ma_nt[i][j]))
                                {
                                    #if DEBUG
                                        debug_print--;
                                    #endif
                                    return NULL;
                                }
                            }
                            else if( con == 0 )// Uklad poprawny wywolujemy rekurencje
                            {
                                Sudoku *pointer = (*rec).try_resolve(maks_old);
                                if(pointer != NULL)// jezeli try_resolve zwrocila cos innego niz null to mamy rozwiazanie -> konczymy
                                {
                                    #if DEBUG
                                        printf("Return\n");
                                        debug_print--;
                                    #endif
                                    delete rec;
                                    return pointer;
                                }
                                else
                                {
                                    failed++;
                                    if(failed == check_mask(ma_nt[i][j]))
                                    {
                                        #if DEBUG
                                            debug_print--;
                                        #endif
                                        return NULL;
                                    }
                                }
                            }
                            else if( con == -1)// mamy rozwiazane zwracamy wskazni do rec
                            {    
                                #if DEBUG
                                    printf("Solution !\n"); 
                                    print_tab(cout,(*rec).ma_nt);
                                    printf("\n");
                                    print_tab(cout,(*rec).ma_num);
                                    debug_print--;
                                #endif
                                return rec;
                            }
                                n++;
                                delete rec;
                        }
                    }
                    if( i + 1 == m_size && j + 1 == m_size)
                    {
                        maks_old++;
                        if(maks_old == m_size)
                            return NULL;
                    }

            }
            return NULL;
        }
        
        inline void update_on_elimination()
        {
            for( int n = 1; n <= m_size; n++)
            {
                for(int i = 0 ; i < m_size ; i++ )
                {
                    elimination_row(i, n);
                    elimination_column(i, n);
                    //elimination_square(i, n);
                }
            }
        }

        inline void elimination_row(int i,int n)
        {
            int put = 0;
            int sum = 0;
            int move = 0;
            for(; move < m_size; move++)
            {
                if(ma_nt[i][move] == 0 || ma_nt[i][move] == -n)
                    return;
                if(  (ma_nt[i][move] & (1<<n)) == 0) 
                {
                    put = move;
                    sum++;
                }
            }
            if( sum == 1)
            {
                #if DEBUG
                    printf("Elimnation row, value = %d, i = %d, j = %d\n",n,i,put);
                #endif
                update(n,i,put);//Jedyna opcja wstawienia
            }
        } 

        inline void elimination_column(int j,int n)
        {
            int put = 0;
            int sum = 0;
            int move = 0;
            for(; move < m_size; move++)
            {
                if(ma_nt[move][j] == 0 || ma_nt[move][j] == -n)
                    return;
                if(  (ma_nt[move][j] & (1<<n)) == 0) 
                {
                    put = move;
                    sum++;
                }
            }
            if( sum == 1)
            {
                #if DEBUG
                    printf("Elimnation column, value = %d, i = %d, j = %d\n",n,put,j);
                #endif
                update(n,put,j);//Jedyna opcja wstawienia
            }
        } 

        inline void elimination_square(int i,int n)
        {
            int sum = 0;
            int sq = sqrt(m_size);// szerokosc kazdego kwadratu 
            int square_i = i%sq; // pozycja i dla podanego kwadratu 
            int square_j = i/sq; // pozycja j dla podanego kwadratu
            int move_i;
            int move_j;
            int put_i;
            int put_j;
            for( move_i = square_i*sq; move_i < (square_i+1)*sq ; move_i++)
                for( move_j = square_j*sq; move_j < (square_j+1)*sq; move_j++)
                {
                    if((ma_nt[move_i][move_j] == 0) || ma_nt[move_i][move_j] == -n )
                        return; 
                    if( (ma_nt[move_i][move_j] > 0) && ( ma_nt[move_i][move_j] & (1<<n)) == 0 ) 
                    {
                        put_i = move_i;
                        put_j = move_j;
                        sum++;
                    }
                }
            if( sum == 1)
            {
                #if DEBUG
                    printf("Elimnation squ, value = %d, i = %d, j = %d\n",n,put_i,put_j);
                #endif
                update(n,put_i,put_j);
            }
        } 

        inline void update_cell(int n,int i,int j)
        {
            ma_nt[i][j]=-n;
            ma_num[i][j]=-1;
            num_puts++;
        }

        inline void update_row(int n,int i,int j)
        {
            for(int move = 0 ; move < m_size ; move++)
            {
                int& temp_num = ma_num[i][move];
                int& temp_nt = ma_nt[i][move];
                if( temp_num != -1 && ( temp_nt & (1<<n)) == 0)
                {
                    temp_nt |= (1 <<n);
                    temp_num++;
                    if(temp_num == m_size-1)
                        update( check(temp_nt),i,move);
                }
            }
        }

        inline void update_column(int n,int i,int j)
        {
            for(int move = 0 ; move < m_size ; move++)
            {
                int& temp_num = ma_num[move][j];
                int& temp_nt = ma_nt[move][j];
                if(temp_num != -1 && (temp_nt & (1 <<n)) == 0)
                {
                    temp_nt |= (1 <<n);
                    temp_num++;
                    if(temp_num == m_size-1)
                        update( check(temp_nt),move,j);
                }

            }
        }

        inline void update_small_square(int n, int i,int j)
        {
            int sq = sqrt(m_size);// szerokosc kazdego trojkata
            int square_i = i/sq; // pozycja i dla podanego trojkata
            int square_j = j/sq; // pozycja j dla podanego trojkata
            for(int move_i = square_i*sq; move_i < (square_i+1)*sq ; move_i++)
                for(int move_j = square_j*sq; move_j < (square_j+1)*sq; move_j++)
                {
                    int& temp_num = ma_num[move_i][move_j];
                    int& temp_nt = ma_nt[move_i][move_j];

                    if( temp_num != -1  && (temp_nt & (1 <<n)) == 0)
                    {
                        temp_nt |= (1 <<n);
                        temp_num++;
                        if(temp_num == m_size-1)
                            update( check(temp_nt),move_i,move_j);
                    }
        
                }
        }
        
        int check(int mask)
        {
            mask = ~mask;
            for(int i = 1 ; i < m_size+1 ; i++)
                if( (mask & (1 << i)) != 0)
                    return i;
            return 0;
        }
                
        int check(int mask, int n)
        {
            mask = ~mask;
            for(int i = 1 ; i < m_size+1 ; i++)
                if( (mask & (1 << i)) != 0)
                {
                    if(!(--n))
                        return i;
                }
            return 0;
        }

        int check_mask(int mask)
        {
            int n =0;
            mask = ~mask;
            for(int i = 1 ; i < m_size+1 ; i++)
                if( (mask & (1 << i)) != 0)
                    n++; 
            return n;
        }


        void update(int n, int i,int j)
        {
            #if DEBUG
                printf("Update: n = %d, i = %d, j = %d\n",n,i,j);
            #endif
            update_cell(n,i,j); 
            update_row(n,i,j);
            update_column(n,i,j);
            update_small_square(n,i,j);
        }

        void print_tab(ostream &a_stream,int** tab)
        {
            for( int i = 0 ; i < m_size ; i++)
            {
                for( int j = 0 ; j < m_size ; j++)
                    a_stream<<tab[i][j]<<"\t";
                a_stream<<endl;
            }
        }
    public:
        /*
         *  Konstruktor 
         *  @param[in]     a_size - wielkość tablicy sudoku n x n 
         */ 
        Sudoku(int a_size):m_size(a_size),m_size2(a_size*a_size)
        {
            ma_cells = new char*[m_size];
            for(int i = 0 ;i < m_size ; i++)
            {
                ma_cells[i] = new char[m_size];
                for(int j = 0; j < m_size ; j++)
                    ma_cells[i][j] = 0;
            }
            ma_nt = new int*[m_size];
            ma_num= new int*[m_size];

            for(int i = 0 ; i < m_size ; i++)
            {
                ma_nt[i] = new int[m_size];
                ma_num[i] = new int[m_size];
                for(int j = 0; j< m_size;j++)
                {
                    ma_nt[i][j] = 0;
                    ma_num[i][j] = 0;
                }
            }
            num_puts = 0;
            num_empty = 0;
        }

        /*
         *  Konstruktor Kopiujący - kopiowanie głebokie
         *  @param[in]     sudoku - obiekt dla którego ma zostać wykonana kopia 
         */ 

        Sudoku(const Sudoku& sudoku):m_size(sudoku.m_size),m_size2(sudoku.m_size2)
        {
            //ma_cells = _cells;
            ma_cells = new char*[m_size];
            for(int i = 0 ;i < m_size ; i++)
            {
                ma_cells[i] = new char[m_size];
                for(int j = 0; j < m_size ; j++)
                    ma_cells[i][j] = sudoku.ma_cells[i][j];
            }

            ma_nt = new int*[m_size];
            ma_num= new int*[m_size];

            for(int i = 0 ; i < m_size ; i++)
            {
                ma_nt[i] = new int[m_size];
                ma_num[i] = new int[m_size];
                for(int j = 0; j< m_size;j++)
                {
                    ma_nt[i][j] = sudoku.ma_nt[i][j];
                    ma_num[i][j] = sudoku.ma_num[i][j];
                }
            }
            num_puts = sudoku.num_puts;
            num_empty = sudoku.num_empty;
        }

        /*
         *  Destruktor 
         */ 

        virtual ~Sudoku()
        {
            if(ma_cells != NULL)
            {
                for(int i = 0 ;i < m_size ; i++)
                    delete [] ma_cells[i]; 
                delete [] ma_cells; 
            }

            for(int i = 0 ; i < m_size ; i++)
            {
                delete [] ma_nt[i];
                delete [] ma_num[i];
            }

            delete [] ma_nt;
            delete [] ma_num;
        }

        /*
         * Pobiera elementy kolejne elementy tablicy z podanego strumienia
         * @param[in] a_stream - strumien z którego będą pobierane dane
         */

        void getFromStream(istream &a_stream )
        {
            int temp;
            for( int i = 0 ; i < m_size ; i++)
                for( int j = 0 ; j < m_size ; j++)
                {
                    a_stream>>temp;
                    ma_cells[i][j]=(int)temp;
                    if(temp == 0)
                        num_empty++;
                }
            #if DEBUG
                printf("Number of empty cells%d\n",num_empty);
            #endif
        }

        /*
         * Wypisuje tablicę wejściową na podane wyjście
         * @param[in] a_stream - strumień wyjściowy 
         */

        void print(ostream &a_stream)
        {
            for( int i = 0 ; i < m_size ; i++)
            {
                for( int j = 0 ; j < m_size ; j++)
                    a_stream<<(int)ma_cells[i][j]<<'\t';
                a_stream<<endl;
            }
        }

        /*
         * Rozwiązuję podany problem sudoku
         * @return 1 - układ udało się rozwiązać - 0 - nie udało się rozwiązać
         */

        int solve()
        {
            for(int i = 0 ; i < m_size ; i++ )
            {    
                for(int j = 0 ; j < m_size ; j++ )
                {
                    if( ma_cells[i][j] != 0)
                    {
                        update(ma_cells[i][j],i,j);
                    }

                }
            }
            update_on_elimination();

            if(check_condition()==1)
            {
                //#if DEBUG
                    printf("Error: uklad sprzeczny\n");
                //#endif
                return -1;
            }

            if( num_puts >= m_size2 )
            {
                #if DEBUG 
                    printf("Recursion don't needed\n");
                #endif
                minus_tab();
            }
            else{ 
                Sudoku* p_sudoku = try_resolve(2);
                if(p_sudoku == NULL)
                {
                    printf("Error: uklad sprzeczny\n");
                    return 0;
                }
                else{
                    #if DEBUG
                        printf("Ok\n");
                    #endif
                    create_solution(p_sudoku);
                }
            }
            print_tab(cout,ma_nt);
            return 0;
        }
        
    protected:
};


int main(int argc,char * argv[])
{
    int i_size = 0;
    cin >> i_size;
    Sudoku sudoku(i_size);
    sudoku.getFromStream(cin);
    sudoku.solve();

    return 0;
}
